//输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，
//它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 
//
// 
//
// 示例： 
//
// 给定一个链表: 1->2->3->4->5, 和 k = 2.
//
//返回链表 4->5. 
// Related Topics 链表 双指针 
// 👍 70 👎 0

package leetcode.editor.cn;

import common.bean.ListNode;
import common.util.MyUtil;

/**
 * Java：链表中倒数第k个节点
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P剑指_offer_22_LianBiaoZhongDaoShuDiKgeJieDianLcof {
    public static void main(String[] args) {
        Solution solution = new P剑指_offer_22_LianBiaoZhongDaoShuDiKgeJieDianLcof().new Solution();
        ListNode head = MyUtil.createNode(1, 2, 3, 4, 5, 6);
        MyUtil.printListNode(solution.getKthFromEnd(head, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
//    /**
//     * 迭代
//     * 时间复杂度 O(n*k)
//     */
//    class Solution {
//        public ListNode getKthFromEnd(ListNode head, int k) {
//            for (ListNode curr = head; curr != null; curr = curr.next) {
//                ListNode temp = curr;
//                for (int i = 0; i <= k; i++) {
//                    if (temp == null) {
//                        if (i == k) {
//                            return curr;
//                        } else {
//                            return null;
//                        }
//                    } else {
//                        temp = temp.next;
//                    }
//                }
//            }
//            return null;
//        }
//    }

    /**
     * 双指针
     * 时间复杂度 O(n)
     */
    class Solution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode far = head, near = head;
            // far指针先走k步
            for (int i = 0; i < k; i++) {
                if (far == null) {
                    return null;
                }
                far = far.next;
            }
            while (far != null) {
                far = far.next;
                near = near.next;
            }
            return near;
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

}